//
// Created by Crev on 24-6-3.
//

#include <queue>
#include <iostream>
#include <utility>
#include <algorithm>

#include "LRMap.h"

#include <iomanip>

#include "global.h"
#include "ProductionManager.h"

LRMap::LRMap(vector<Production> productions, const map<string, Character*>& nameToCharacter,
             const map<string, vector<Production>>& nameToProductions,
             const bool& isLA): nameToCharacter(nameToCharacter), nameToProductions(nameToProductions) {
    // 获取第一个文法语句
    Production originStart = productions[0];
    // 新文法开始语句的右侧
    vector<Character*> newStartRight;
    // 新文法开始语句右侧是旧文法开始语句的左侧非终结符
    newStartRight.emplace_back(originStart.left);
    // 构造新的文法开始语句
    // 左侧是非终结符，符号是旧文法开始语句左侧的非终结符的符号加上一个 '
    // 建立语法树时，为了在使用本文法语句规约时保留右侧的原文法开始符号，设置建点类型为将右侧的原文法开始符号设置为根，这样根节点就不会带上 '
    Production newStart(new Character(originStart.left->name + "'"), newStartRight, 0, {BUILD_TYPE_ROOT});
    // 构造后插入文法开始位置
    productions.emplace(productions.begin(), newStart);
    this->productions = productions;
    this->isLA = isLA;
    // 初始化包含所有终结符符号的列表
    initAllChars();
    // 建DFA图，isLA配置是否按LALR(1)的构造方法建立DFA图，否则按LR(1)方法建立
    buildMap();
    // 初始化DFA表格
    initTable();
}

/**
 * 打印DFA表格
 */
void LRMap::showTable() const {
    if (isLA) {
        cout << "-----------------------LALR(1)分析表------------------------" << endl;
    }
    else {
        cout << "--------------------------DFA表格---------------------------" << endl;
    }
    // 计算每个列的最大宽度
    vector<int> colWidths;
    colWidths.reserve(allChars.size());
    for (const auto allChar : allChars) {
        colWidths.emplace_back(allChar->name.length());
    }
    // 打印表头
    cout << setw(5) << left << "/";
    for (int i = 0; i < allChars.size(); i++) {
        cout << setw(colWidths[i] + 2) << left << allChars[i]->name;
    }
    cout << endl;
    for (int i = 0; i < table.size(); i++) {
        cout << setw(5) << left << i;
        for (int j = 0; j < table[i].size(); j++) {
            cout << setw(colWidths[j] + 2) << left << table[i][j];
        }
        cout << endl;
    }
}

/**
 * 打印DFA节点内容和出边情况
 */
void LRMap::showMap() const {
    if (isLA) {
        cout << "--------------------------LALR(1)--------------------------" << endl;
    }
    else {
        cout << "---------------------------LR(1)---------------------------" << endl;
    }
    for (const auto& node : allNodes) {
        cout << "Node[" << node->index << "]" << endl;
        // 打印该点的信息
        for (const auto& p : node->productionsInNode) {
            cout << p << endl;
        }
        const LREdge* e = node->firstEdge;
        int eCount = 0;
        if (e != nullptr)cout << endl << "Edges:" << endl;
        while (e != nullptr) {
            cout << "e[" << eCount++ << "]\t---- " << e->nameOnEdge << " ---->\t";
            const LRNode* nextNode = allNodes[e->endIndex];
            cout << "Node[" << nextNode->index << "]";
            e = e->nextEdge;
            // 如果有指向自己的边，就不加进来了，不然会死循环
            if (node->index == nextNode->index) cout << " *self*";
            cout << endl;
        }
        cout << "-----------------------------------------------------------" << endl;
    }
}

/**
 * 初始化包含所有终结符和非终结符符号的列表allChars和包含所有终结符符号名字的集合allEndCharNames（后者用于Parser的解析特判）
 */
void LRMap::initAllChars() {
    // 去重
    set<Character*> uniqueChars;
    for (auto& production : productions) {
        uniqueChars.insert(production.left);
        for (auto c : production.right) {
            uniqueChars.insert(c);
        }
    }
    for (auto c : uniqueChars) {
        allChars.push_back(c);
        // 初始化终结符名字集合
        if (c->isEnd && c->name != NULL_CHARACTER) {
            allEndCharNames.insert(c->name);
        }
    }
    // 让数组中非终结符处于后面
    sort(allChars.begin(), allChars.end(), [](const Character* c1, const Character* c2) {
        if (c1->isEnd != c2->isEnd) {
            return c1->isEnd > c2->isEnd;
        }
        return c1->name < c2->name;
    });
    // 结束符号放最前面
    allChars.insert(allChars.begin(), new Character(END_CHARACTER, true));
}

/**
 * 初始化DFA表格
 */
void LRMap::initTable() {
    // 按顺序给字符标号
    map<string, int> nameToIndex;
    int index = 0;
    for (const auto& c : allChars) {
        nameToIndex[c->name] = index++;
    }
    // 给table指定容量
    for (int i = 0; i < allNodes.size(); i++) {
        table.emplace_back(allChars.size());
    }
    // tableMap则是只用指定行容量
    tableMap.resize(allNodes.size());
    // 遍历所有的点
    for (int i = 0; i < allNodes.size(); i++) {
        // 看点里面是否有可以规约的
        for (const auto& p : allNodes[i]->productionsInNode) {
            if (p.pointIndex == p.right.size()) {
                // 到达结束状态了
                for (const auto& c : p.expectationSet) {
                    // 遇到expectationSet集合中的符号可以规约
                    table[i][nameToIndex[c->name]] = "r" + to_string(p.productionIndex);
                    // tableMap
                    tableMap[i][c->name] = table[i][nameToIndex[c->name]];
                }
            }
        }
        // 遍历点连接的边
        const LREdge* e = allNodes[i]->firstEdge;
        while (e != nullptr) {
            // LALR(1)的终结符推导用s，非终结符推导用g
            string tag = nameToCharacter[e->nameOnEdge]->isEnd ? "s" : "g";
            table[i][nameToIndex[e->nameOnEdge]] = tag + to_string(e->endIndex);
            // tableMap
            tableMap[i][e->nameOnEdge] = table[i][nameToIndex[e->nameOnEdge]];
            e = e->nextEdge;
        }
    }
    // 最后栈底的0号状态遇到文法开始符号到达ac状态
    table[0][nameToIndex[productions[0].left->name]] = "ac";
    // tableMap
    tableMap[0][productions[0].left->name] = table[0][nameToIndex[productions[0].left->name]];
}

/**
 * 构建DFA图，isLA为true则按LALR(1)的构造方法建立DFA图，否则按LR(1)方法建立（区别主要在于对于两个点是否为同一个点的判断逻辑不同）
 */
void LRMap::buildMap() {
    // 创建第一个节点(这样也可保证0下标一定是起始节点)
    vector<Production> startP;
    // 新文法开始语句的expectationSet中只有结束符号，结束符号在符号列表最前面
    productions[0].expectationSet.insert(allChars[0]);
    startP.push_back(productions[0]);
    // 生成第一个点中的内容
    auto productionsInNode = generateAllProductionsFrom(startP);
    // 加入到点集中
    allNodes.push_back(new LRNode(productionsInNode, 0));
    // 加入队列生成DFA图
    queue<LRNode*> qu;
    qu.push(allNodes[0]);
    while (!qu.empty()) {
        const auto front = qu.front();
        // showMap();
        qu.pop();
        // 遍历看是否还需要生成节点
        // .后面的字符可能是相同的，为了不引出相同的边，需要先把走相同的边的文法语句集合到一起
        map<string, vector<Production>> includedNameToProductions;
        for (auto p : front->productionsInNode) {
            if (p.pointIndex < p.right.size()) {
                // 还需要生成
                string edgeName = p.right[p.pointIndex]->name; // 出边的名字
                p.pointIndex++; // 移动点的位置
                includedNameToProductions[edgeName].push_back(p);
            }
        }
        for (const auto& n2p : includedNameToProductions) {
            // first是当前的出边名，second是这个点的初始文法语句列表
            // 用初始的几句文法获取节点的内容
            productionsInNode = generateAllProductionsFrom(n2p.second);
            // 依据内容中文法语句的拼接结果判断是否已经创建过相同的节点
            string str;
            for (const auto& p : productionsInNode) {
                // 不是LALR(1)的话去重标准需要包括后面的expectationSet
                str += p.toString(!isLA);
            }
            LRNode* toNode;
            if (pStringToNode.count(str)) {
                // 已经有相同的节点了
                toNode = pStringToNode[str];
                // 是LALR(1)的话需要更新expectationSet，将expectationSet取并集
                if (isLA) {
                    // 需要通过判断expectationSet集合是否有更新来判断是否需要通过该点重新生成DFA图
                    // 因为如果expectationSet集合更新了，说明原本相同的点的expectationSet集合较小，如果不重新进入队列生成点，则原本相同的点生成的后续节点的expectationSet集合会缺少元素
                    bool needToReGenerate = false; // 标记是否需要当作新的点重新生成
                    // 因为str标记相同，文法顺序自然相同，直接使用下标逐个更新即可
                    for (int i = 0; i < toNode->productionsInNode.size(); i++) {
                        // 记录更新前的大小
                        const size_t preSize = toNode->productionsInNode[i].expectationSet.size();
                        // 更新集合
                        toNode->productionsInNode[i].expectationSet.insert(
                            productionsInNode[i].expectationSet.begin(), productionsInNode[i].expectationSet.end());
                        if (preSize < toNode->productionsInNode[i].expectationSet.size()) {
                            // 如果expectationSet集合变大了，则需要重新生成
                            needToReGenerate = true;
                        }
                    }
                    if (needToReGenerate) {
                        // 主体和原来的点相同的新点拥有原来的点expectationSet集合中没有的元素，则将合并后的点（expectationSet集合是二者并集的新点）重新进入队列生成DFA图
                        toNode->firstEdge = nullptr; // 重新连边，不然会有很多重复的边（因为该点会重新生成出边）
                        // 去掉原来的点在边集里的边
                        allEdges.erase(remove_if(allEdges.begin(), allEdges.end(), [toNode](const LREdge* e) {
                            // return e->startIndex == toNode->index;
                            if (e->startIndex == toNode->index) {
                                delete e; // 不能只是从列表里删除，还要delete
                                return true;
                            }
                            return false;
                        }), allEdges.end());
                        // 重新入队
                        qu.push(toNode);
                    }
                }
            }
            else {
                // 没有创建过这个节点
                toNode = new LRNode(productionsInNode, static_cast<int>(allNodes.size()));
                // 存入列表
                allNodes.push_back(toNode);
                // 新创建的点加入队列
                qu.push(toNode);
            }
            // 更新映射
            pStringToNode[str] = toNode;
            // 邻接表操作，first是边上的名
            auto* ePtr = new LREdge(n2p.first, front->index, toNode->index);
            ePtr->nextEdge = front->firstEdge;
            front->firstEdge = ePtr;
            // 存边
            allEdges.push_back(ePtr);
        }
    }
    // cout << "allEdge size: " << allEdges.size() << endl;
}

/**
 * 由一组文法语句(productions)引发其他文法语句的引入，返回最后的所有文法语句
 * 文法在主体相同时视为同一个文法，会将expectationSet集合合并，而不是新增文法到列表中
 * @param originProductions 文法语句列表
 * @return 包含此文法语句列表及其引发的全部文法语句的集合，所有文法语句均已求得expectationSet集合
 */
vector<Production> LRMap::generateAllProductionsFrom(const vector<Production>& originProductions) {
    // 原先的文法保留
    vector<Production> result(originProductions);
    // 将文法推入队列
    queue<Production> qu;
    for (const auto& p : result) qu.push(p);
    while (!qu.empty()) {
        auto production = qu.front();
        qu.pop();
        // 对于每个新增的文法语句，看此时的.下标所处的符号是否为非终结符，是的话需要尝试引入对应的文法语句
        // 合法性判断
        if (production.pointIndex < production.right.size()) {
            const Character* charAtIndex = production.right[production.pointIndex];
            if (!charAtIndex->isEnd) {
                // 需要是非终结符
                // 计算出expectationSet
                // 位置从.坐标之后一个位置到结束
                vector<Character*> charsAfterN(production.right.begin() + static_cast<int>(production.pointIndex) + 1,
                                               production.right.end());
                auto expectationSet = ProductionManager::calcExpectationSet(charsAfterN, production.expectationSet);
                // 找到该非终结符的所有文法语句，尝试引入
                for (auto p : nameToProductions[charAtIndex->name]) {
                    // 每个的expectationSet都是相同的
                    p.expectationSet.insert(expectationSet.begin(), expectationSet.end());
                    // 遍历结果集判断该文法是否属于新生成的文法
                    bool isNewProduction = true;
                    int pos = 0; // 记录下标，如果是相同的文法的话需要更新expectationSet集合
                    for (; pos < result.size(); pos++) {
                        // 对于单个点内的文法是否相同的判断逻辑，LALR(1)和LR(1)是相同的
                        // 文法的主体相同则视为相同文法，toString函数传递false则不将expectationSet集合加入到标记字符串中
                        if (result[pos].toString(false) == p.toString(false)) {
                            // 结果集中有相同文法，标记false
                            isNewProduction = false;
                            break;
                        }
                    }
                    if (isNewProduction) {
                        // 是新生成的文法则存入结果集，并加入队列尝试引入新文法
                        result.push_back(p);
                        qu.push(p);
                    }
                    else {
                        // 是原先就有的文法，则expectationSet集合需要合并
                        // 如果expectationSet集合成功更新，则该文法需要重新入队来引入文法，否则原先该文法引入的文法的expectationSet集合会缺少元素
                        // 记录更新前的大小
                        const size_t preSize = result[pos].expectationSet.size();
                        // 更新集合
                        result[pos].expectationSet.insert(expectationSet.begin(), expectationSet.end());
                        if (preSize < result[pos].expectationSet.size()) {
                            // 如果expectationSet集合变大了，则需要重新入队
                            qu.push(p);
                        }
                    }
                }
            }
        }
    }
    return result;
}
